package lc;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Q556 {
    public int nextGreaterElement(int n) {
        char[] chars = String.valueOf(n).toCharArray();
        // 字符串排序，下一个更大的字符串排列
        int i = chars.length - 2;
        while (i >= 0 && chars[i] >= chars[i + 1]) {
            i --;
        }
        if (i == -1) {
            return -1;
        }
        // 交换
        int j = chars.length - 1;
        while (j >= 0 && chars[i] >= chars[j]) {
            j--;
        }
        // 交换i跟j，然后将中间的翻转
        swap(chars, i, j);
        reverse(chars, i + 1);
        long ans = Long.parseLong(new String(chars));
        return ans > Integer.MAX_VALUE ? -1 : (int) ans;
    }

    public void reverse(char[] nums, int begin) {
        int i = begin, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    public void swap(char[] nums, int i, int j) {
        char temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
